home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1995 January / macformat-020.iso / Shareware City / Developers / OutOfPhase1.01Source / OutOfPhase Folder / PeepholeOptimizer.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-10-01  |  15.5 KB  |  400 lines  |  [TEXT/KAHL]
  1. /* PeepholeOptimizer.c */
  2. /*****************************************************************************/
  3. /*                                                                           */
  4. /*    Out Of Phase:  Digital Music Synthesis on General Purpose Computers    */
  5. /*    Copyright (C) 1994  Thomas R. Lawrence                                 */
  6. /*                                                                           */
  7. /*    This program is free software; you can redistribute it and/or modify   */
  8. /*    it under the terms of the GNU General Public License as published by   */
  9. /*    the Free Software Foundation; either version 2 of the License, or      */
  10. /*    (at your option) any later version.                                    */
  11. /*                                                                           */
  12. /*    This program is distributed in the hope that it will be useful,        */
  13. /*    but WITHOUT ANY WARRANTY; without even the implied warranty of         */
  14. /*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the          */
  15. /*    GNU General Public License for more details.                           */
  16. /*                                                                           */
  17. /*    You should have received a copy of the GNU General Public License      */
  18. /*    along with this program; if not, write to the Free Software            */
  19. /*    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.              */
  20. /*                                                                           */
  21. /*    Thomas R. Lawrence can be reached at tomlaw@world.std.com.             */
  22. /*                                                                           */
  23. /*****************************************************************************/
  24.  
  25. #include "MiscInfo.h"
  26. #include "Audit.h"
  27. #include "Debug.h"
  28. #include "Definitions.h"
  29.  
  30. #define SHOW_ME_OPCODEREC  /* we need to see the contents of opcode records */
  31. #include "PeepholeOptimizer.h"
  32. #include "PcodeObject.h"
  33. #include "Memory.h"
  34.  
  35.  
  36. /* this routine scans the entire code block to see if any branches are made */
  37. /* to any but the first instruction specified in the run of instructions. */
  38. /* Start points to the first instruction, Extent specifies the number of WORDS */
  39. /* (not instructions).  Branches MAY point to Prog[Start], however. */
  40. static MyBoolean        NoBranchToInterior(OpcodeRec* Prog, long Length,
  41.                                             long Start, long Extent)
  42.     {
  43.         long                            Scan;
  44.  
  45.         for (Scan = 0; Scan < Length; Scan += GetInstructionLength(Prog[Scan].Opcode))
  46.             {
  47.                 PRNGCHK(Prog,&(Prog[Scan]),sizeof(Prog[Scan]));
  48.                 if ((Prog[Scan].Opcode == epBranchUnconditional)
  49.                     || (Prog[Scan].Opcode == epBranchIfZero)
  50.                     || (Prog[Scan].Opcode == epBranchIfNotZero))
  51.                     {
  52.                         /* branch operation detected, test index */
  53.                         PRNGCHK(Prog,&(Prog[Scan + 1]),sizeof(Prog[Scan + 1]));
  54.                         if ((Prog[Scan + 1].ImmediateInteger > Start)
  55.                             && (Prog[Scan + 1].ImmediateInteger < Start + Extent))
  56.                             {
  57.                                 /* branch to interior found, so return false. */
  58.                                 return False;
  59.                             }
  60.                     }
  61.             }
  62.         ERROR(Scan != Length,PRERR(ForceAbort,
  63.             "NoBranchToInterior:  internal instruction alignment error"));
  64.         return True;
  65.     }
  66.  
  67.  
  68. /* this routine eliminates the specified segment of code from the program */
  69. /* and updates all branches pointing to areas beyond it.  The new length */
  70. /* is returned.  it also disposes of any additional storage used by the */
  71. /* instructions being deleted */
  72. static long                    DropCodeSegment(OpcodeRec* Prog, long Length,
  73.                                             long Start, long Extent)
  74.     {
  75.         long                            Scan;
  76.  
  77.         /* first, patch up branches */
  78.         for (Scan = 0; Scan < Length; Scan += GetInstructionLength(Prog[Scan].Opcode))
  79.             {
  80.                 /* looking for branch instructions */
  81.                 PRNGCHK(Prog,&(Prog[Scan]),sizeof(Prog[Scan]));
  82.                 if ((Prog[Scan].Opcode == epBranchUnconditional)
  83.                     || (Prog[Scan].Opcode == epBranchIfZero)
  84.                     || (Prog[Scan].Opcode == epBranchIfNotZero))
  85.                     {
  86.                         /* found a branch instruction.  does it need to be patched? */
  87.                         PRNGCHK(Prog,&(Prog[Scan + 1]),sizeof(Prog[Scan + 1]));
  88.                         if (Prog[Scan + 1].ImmediateInteger > Start)
  89.                             {
  90.                                 /* branch is beyond segment being dropped, so decrement it's address */
  91.                                 /* by the length of the segment */
  92.                                 Prog[Scan + 1].ImmediateInteger -= Extent;
  93.                             }
  94.                     }
  95.             }
  96.         ERROR(Scan != Length,PRERR(ForceAbort,
  97.             "DropCodeSegment:  internal instruction alignment error:  branch resolve phase"));
  98.         /* next, dispose of additional memory owned by the instructions that */
  99.         /* are being deleted */
  100.         for (Scan = Start; Scan < Start + Extent;
  101.             Scan += GetInstructionLength(Prog[Scan].Opcode))
  102.             {
  103.                 switch (Prog[Scan].Opcode)
  104.                     {
  105.                         case epFuncCallUnresolved: /* <opcode> ^"<functionname>" ^[paramlist] <returntype> <reserved> */
  106.                         case epFuncCallResolved: /* <opcode> ^"<functionname>" ^[paramlist] <returntype> ^<OpcodeRec> */
  107.                             PRNGCHK(Prog,&(Prog[Scan + 1]),sizeof(Prog[Scan + 1]));
  108.                             ReleasePtr(Prog[Scan + 1].ImmediateString);
  109.                             PRNGCHK(Prog,&(Prog[Scan + 2]),sizeof(Prog[Scan + 2]));
  110.                             ReleasePtr((char*)(Prog[Scan + 2].DataTypeArray));
  111.                             break;
  112.                         case epOperationBooleanEqual: /* <opcode> */
  113.                         case epOperationBooleanNotEqual:
  114.                         case epOperationBooleanAnd:
  115.                         case epOperationBooleanOr:
  116.                         case epOperationBooleanNot:
  117.                         case epOperationBooleanToInteger:
  118.                         case epOperationBooleanToFloat:
  119.                         case epOperationBooleanToDouble:
  120.                         case epOperationBooleanToFixed:
  121.                         case epOperationIntegerAdd:
  122.                         case epOperationIntegerSubtract:
  123.                         case epOperationIntegerNegation:
  124.                         case epOperationIntegerMultiply:
  125.                         case epOperationIntegerDivide:
  126.                         case epOperationIntegerModulo:
  127.                         case epOperationIntegerShiftLeft:
  128.                         case epOperationIntegerShiftRight:
  129.                         case epOperationIntegerGreaterThan:
  130.                         case epOperationIntegerLessThan:
  131.                         case epOperationIntegerGreaterThanOrEqual:
  132.                         case epOperationIntegerLessThanOrEqual:
  133.                         case epOperationIntegerEqual:
  134.                         case epOperationIntegerNotEqual:
  135.                         case epOperationIntegerAbs:
  136.                         case epOperationIntegerToBoolean:
  137.                         case epOperationIntegerToFloat:
  138.                         case epOperationIntegerToDouble:
  139.                         case epOperationIntegerToFixed:
  140.                         case epOperationFloatAdd:
  141.                         case epOperationFloatSubtract:
  142.                         case epOperationFloatNegation:
  143.                         case epOperationFloatMultiply:
  144.                         case epOperationFloatDivide:
  145.                         case epOperationFloatGreaterThan:
  146.                         case epOperationFloatLessThan:
  147.                         case epOperationFloatGreaterThanOrEqual:
  148.                         case epOperationFloatLessThanOrEqual:
  149.                         case epOperationFloatEqual:
  150.                         case epOperationFloatNotEqual:
  151.                         case epOperationFloatAbs:
  152.                         case epOperationFloatToBoolean:
  153.                         case epOperationFloatToInteger:
  154.                         case epOperationFloatToDouble:
  155.                         case epOperationFloatToFixed:
  156.                         case epOperationDoubleAdd:
  157.                         case epOperationDoubleSubtract:
  158.                         case epOperationDoubleNegation:
  159.                         case epOperationDoubleMultiply:
  160.                         case epOperationDoubleDivide:
  161.                         case epOperationDoubleGreaterThan:
  162.                         case epOperationDoubleLessThan:
  163.                         case epOperationDoubleGreaterThanOrEqual:
  164.                         case epOperationDoubleLessThanOrEqual:
  165.                         case epOperationDoubleEqual:
  166.                         case epOperationDoubleNotEqual:
  167.                         case epOperationDoubleAbs:
  168.                         case epOperationDoubleToBoolean:
  169.                         case epOperationDoubleToInteger:
  170.                         case epOperationDoubleToFloat:
  171.                         case epOperationDoubleToFixed:
  172.                         case epOperationDoubleSin:
  173.                         case epOperationDoubleCos:
  174.                         case epOperationDoubleTan:
  175.                         case epOperationDoubleAtan:
  176.                         case epOperationDoubleLn:
  177.                         case epOperationDoubleExp:
  178.                         case epOperationDoubleSqrt:
  179.                         case epOperationDoublePower:
  180.                         case epOperationFixedAdd:
  181.                         case epOperationFixedSubtract:
  182.                         case epOperationFixedNegation:
  183.                         case epOperationFixedMultiply:
  184.                         case epOperationFixedDivide:
  185.                         case epOperationFixedShiftLeft:
  186.                         case epOperationFixedShiftRight:
  187.                         case epOperationFixedGreaterThan:
  188.                         case epOperationFixedLessThan:
  189.                         case epOperationFixedGreaterThanOrEqual:
  190.                         case epOperationFixedLessThanOrEqual:
  191.                         case epOperationFixedEqual:
  192.                         case epOperationFixedNotEqual:
  193.                         case epOperationFixedAbs:
  194.                         case epOperationFixedToBoolean:
  195.                         case epOperationFixedToInteger:
  196.                         case epOperationFixedToFloat:
  197.                         case epOperationFixedToDouble:
  198.                         case epGetBooleanArraySize: /* <opcode> */
  199.                         case epGetIntegerArraySize:
  200.                         case epGetFloatArraySize:
  201.                         case epGetDoubleArraySize:
  202.                         case epGetFixedArraySize:
  203.                         case epReturnFromSubroutine: /* <opcode> */
  204.                         case epLoadImmediateNILArray: /* <opcode> */
  205.                         case epMakeBooleanArray: /* <opcode> */
  206.                         case epMakeIntegerArray:
  207.                         case epMakeFloatArray:
  208.                         case epMakeDoubleArray:
  209.                         case epMakeFixedArray:
  210.                         case epStackPop: /* <opcode> */
  211.                         case epDuplicate: /* <opcode> */
  212.                         case epNop: /* <opcode> */
  213.                         case epStackAllocate: /* <opcode> */
  214.                         case epResizeBooleanArray2: /* <opcode> */
  215.                         case epResizeIntegerArray2:
  216.                         case epResizeFloatArray2:
  217.                         case epResizeDoubleArray2:
  218.                         case epResizeFixedArray2:
  219.                         case epStoreBooleanIntoArray2: /* <opcode> */
  220.                         case epStoreIntegerIntoArray2:
  221.                         case epStoreFloatIntoArray2:
  222.                         case epStoreDoubleIntoArray2:
  223.                         case epStoreFixedIntoArray2:
  224.                         case epLoadBooleanFromArray2: /* <opcode> */
  225.                         case epLoadIntegerFromArray2:
  226.                         case epLoadFloatFromArray2:
  227.                         case epLoadDoubleFromArray2:
  228.                         case epLoadFixedFromArray2:
  229.                         case epOperationBooleanXor:
  230.                         case epOperationIntegerAnd:
  231.                         case epOperationFixedAnd:
  232.                         case epOperationIntegerOr:
  233.                         case epOperationFixedOr:
  234.                         case epOperationIntegerXor:
  235.                         case epOperationFixedXor:
  236.                         case epOperationIntegerImpreciseDivide:
  237.                         case epOperationFloatShiftLeft:
  238.                         case epOperationDoubleShiftLeft:
  239.                         case epOperationFloatShiftRight:
  240.                         case epOperationDoubleShiftRight:
  241.                         case epOperationIntegerNot:
  242.                         case epOperationDoubleAsin:
  243.                         case epOperationDoubleAcos:
  244.                         case epOperationDoubleSqr:
  245.                         case epOperationTestIntegerNegative:
  246.                         case epOperationTestFloatNegative:
  247.                         case epOperationTestDoubleNegative:
  248.                         case epOperationTestFixedNegative:
  249.                         case epOperationGetSignInteger:
  250.                         case epOperationGetSignFloat:
  251.                         case epOperationGetSignDouble:
  252.                         case epOperationGetSignFixed:
  253.                         case epStackPopMultiple: /* <opcode> <numwords> */
  254.                         case epStackDeallocateUnder: /* <opcode> <numwords> */
  255.                         case epOperationBooleanToIntegerBuried:  /* <opcode> <stackindex> */
  256.                         case epOperationBooleanToFloatBuried:
  257.                         case epOperationBooleanToDoubleBuried:
  258.                         case epOperationBooleanToFixedBuried:
  259.                         case epOperationIntegerToBooleanBuried:
  260.                         case epOperationIntegerToFloatBuried:
  261.                         case epOperationIntegerToDoubleBuried:
  262.                         case epOperationIntegerToFixedBuried:
  263.                         case epOperationFloatToBooleanBuried:
  264.                         case epOperationFloatToIntegerBuried:
  265.                         case epOperationFloatToDoubleBuried:
  266.                         case epOperationFloatToFixedBuried:
  267.                         case epOperationDoubleToBooleanBuried:
  268.                         case epOperationDoubleToIntegerBuried:
  269.                         case epOperationDoubleToFloatBuried:
  270.                         case epOperationDoubleToFixedBuried:
  271.                         case epOperationFixedToBooleanBuried:
  272.                         case epOperationFixedToIntegerBuried:
  273.                         case epOperationFixedToFloatBuried:
  274.                         case epOperationFixedToDoubleBuried:
  275.                         case epBranchUnconditional: /* <opcode> <branchoffset> */
  276.                         case epBranchIfZero:
  277.                         case epBranchIfNotZero:
  278.                         case epStoreIntegerOnStack: /* <opcode> <stackindex> */
  279.                         case epStoreFloatOnStack:
  280.                         case epStoreDoubleOnStack:
  281.                         case epStoreArrayOnStack:
  282.                         case epLoadIntegerFromStack:
  283.                         case epLoadFloatFromStack:
  284.                         case epLoadDoubleFromStack:
  285.                         case epLoadArrayFromStack:
  286.                         case epLoadImmediateInteger: /* <opcode> <integer>; also used for boolean & fixed */
  287.                             break;
  288.                         case epLoadImmediateFloat: /* <opcode> ^<float> */
  289.                             PRNGCHK(Prog,&(Prog[Scan + 1]),sizeof(Prog[Scan + 1]));
  290.                             ReleasePtr((char*)(Prog[Scan + 1].ImmediateFloat));
  291.                             break;
  292.                         case epLoadImmediateDouble: /* <opcode> ^<double> */
  293.                             PRNGCHK(Prog,&(Prog[Scan + 1]),sizeof(Prog[Scan + 1]));
  294.                             ReleasePtr((char*)(Prog[Scan + 1].ImmediateDouble));
  295.                             break;
  296.                         case epGetSampleLeftArray: /* <opcode> ^"<namestring>" */
  297.                         case epGetSampleRightArray:
  298.                         case epGetSampleMonoArray:
  299.                             PRNGCHK(Prog,&(Prog[Scan + 1]),sizeof(Prog[Scan + 1]));
  300.                             ReleasePtr((char*)(Prog[Scan + 1].ImmediateString));
  301.                             break;
  302.                         case epErrorTrap: /* <opcode> ^"<errorstring>" */
  303.                             PRNGCHK(Prog,&(Prog[Scan + 1]),sizeof(Prog[Scan + 1]));
  304.                             ReleasePtr(Prog[Scan + 1].ImmediateString);
  305.                             break;
  306.                         default:
  307.                             EXECUTE(PRERR(ForceAbort,"DropCodeSegment:  unknown opcode"));
  308.                     }
  309.             }
  310.         ERROR(Scan != Start + Extent,PRERR(ForceAbort,
  311.             "DropCodeSegment:  internal instruction alignment error:  dispose phase"));
  312.         /* now, delete the code segment */
  313.         for (Scan = Start; Scan < Length - Extent; Scan += 1)
  314.             {
  315.                 PRNGCHK(Prog,&(Prog[Scan]),sizeof(Prog[Scan]));
  316.                 PRNGCHK(Prog,&(Prog[Scan + Extent]),sizeof(Prog[Scan + Extent]));
  317.                 Prog[Scan] = Prog[Scan + Extent];
  318.             }
  319.         /* now, erase that little bit at the end */
  320.         for (Scan = Length - Extent; Scan < Length; Scan += 1)
  321.             {
  322.                 PRNGCHK(Prog,&(Prog[Scan]),sizeof(Prog[Scan]));
  323.                 Prog[Scan].Opcode = epNop;
  324.             }
  325.         /* now, return the new code length */
  326.         return Length - Extent;
  327.     }
  328.  
  329.  
  330. /* this routine looks for indivisible dup/pop operations (with no interior */
  331. /* branches) and eliminates them.  *Flag is set if some change was made, and the */
  332. /* new length of Prog[] is returned. */
  333. static long                    EliminateDupPop(OpcodeRec* Prog, long Length, MyBoolean* Flag)
  334.     {
  335.         long                            Scan;
  336.  
  337.         Scan = 0;
  338.         while (Scan < Length)
  339.             {
  340.                 /* look to see if this part can be dropped.  if it can, we don't increment */
  341.                 /* Scan so that we can look at the part that will be moved into where this */
  342.                 /* is as well.  otherwise, we do increment */
  343.                 if ((Prog[Scan].Opcode == epDuplicate)
  344.                     && (Prog[Scan + 1].Opcode == epStackPop)
  345.                     && NoBranchToInterior(Prog,Length,Scan,2))
  346.                     {
  347.                         /* found one! */
  348.                         Length = DropCodeSegment(Prog,Length,Scan,2);
  349.                         *Flag = True;
  350.                     }
  351.                  else
  352.                     {
  353.                         /* increment only if not found */
  354.                         Scan += GetInstructionLength(Prog[Scan].Opcode);
  355.                     }
  356.             }
  357.         ERROR(Scan != Length,PRERR(ForceAbort,
  358.             "EliminateDupPop:  internal instruction alignment error"));
  359.         return Length;
  360.     }
  361.  
  362.  
  363. /* perform the optimizations */
  364. void                                OptimizePcode(PcodeRec* ThePcode)
  365.     {
  366.         OpcodeRec*                Prog;
  367.         long                            Length;
  368.         MyBoolean                    OptimizationFound;
  369.  
  370.         /* obtain the important information */
  371.         Prog = GetOpcodeFromPcode(ThePcode);
  372.         Length = GetNumberOfValidCellsInPcode(ThePcode);
  373.  
  374.         /* begin the optimization loop */
  375.         do
  376.             {
  377.                 /* we go until no more optimizations can be found, so we clear this */
  378.                 /* flag.  at the end, if the flag is set, we'll check again. */
  379.                 OptimizationFound = False;
  380.  
  381.                 Length = EliminateDupPop(Prog,Length,&OptimizationFound);
  382.             } while (OptimizationFound);
  383.  
  384.         /* resize the code block to eliminate any empty cells at the end */
  385.         if (PtrSize((char*)Prog) != Length * sizeof(OpcodeRec))
  386.             {
  387.                 OpcodeRec*                Temp;
  388.  
  389.                 Temp = (OpcodeRec*)ResizePtr((char*)Prog,Length * sizeof(OpcodeRec));
  390.                 if (Temp != NIL)
  391.                     {
  392.                         UpdateOpcodeInPcode(ThePcode,Temp,Length);
  393.                     }
  394.                 /* if we couldn't resize it, then it's just too bad.  the evaluator */
  395.                 /* doesn't really depend on the length of the opcode for anything, so */
  396.                 /* it doesn't matter.  (DisposePcode does, but the end is erased with */
  397.                 /* nops, so it shouldn't delete anything important.) */
  398.             }
  399.     }
  400.